#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 根据先序遍历和中序遍历序列构造二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder);

// 辅助函数，根据先序遍历和中序遍历序列构造二叉树
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd, unordered_map<int, int>& indexMap);

// 打印二叉树（中序遍历）
void inorderTraversal(TreeNode* root);

int main() {
    // 给定的先序遍历和中序遍历序列
    vector<int> preorder = {3, 9, 20, 15, 7};
    vector<int> inorder = {9, 3, 15, 20, 7};

    // 构造二叉树
    TreeNode* root = buildTree(preorder, inorder);

    // 打印构造的二叉树（中序遍历）
    cout << "Inorder Traversal of the Constructed Tree: ";
    inorderTraversal(root);
    cout << endl;

    return 0;
}

// 根据先序遍历和中序遍历序列构造二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> indexMap;
    for (int i = 0; i < inorder.size(); i++) {
        indexMap[inorder[i]] = i;
    }
    return buildTreeHelper(preorder, 0, preorder.size(), inorder, 0, inorder.size(), indexMap);
}

// 辅助函数，根据先序遍历和中序遍历序列构造二叉树
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd, unordered_map<int, int>& indexMap) {
    if (preStart >= preEnd || inStart >= inEnd) {
        return nullptr;
    }
    int rootVal = preorder[preStart];
    TreeNode* root = new TreeNode(rootVal);
    int rootIndex = indexMap[rootVal];
    int leftSubtreeSize = rootIndex - inStart;
    root->left = buildTreeHelper(preorder, preStart + 1, preStart + 1 + leftSubtreeSize, inorder, inStart, rootIndex, indexMap);
    root->right = buildTreeHelper(preorder, preStart + 1 + leftSubtreeSize, preEnd, inorder, rootIndex + 1, inEnd, indexMap);
    return root;
}

// 打印二叉树（中序遍历）
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}
